This paper is concerned with the optimization of the cutting pattern for the lobes of pumpkin-shaped balloon structures. Pumpkin balloons, currently developed for the NASA Ultra-Long Duration Balloon (ULDB), consist of stiff meridional tendons that constrain a thin plastic film. The present study shows that the maximum stability of pumpkin balloons is reached if their surface area is minimized under a given stress constraint. This results in fully stressed designs that in some cases have a total surface area smaller than a smooth isotensoid surface, without increasing the maximum stresses in the film. The resulting designs are likely to avoid the shape instabilities that have been observed in balloons with a high surface area to volume rati...